Skip to main content

Plus One

Problem Description​

Given a non-negative number represented as a list of digits, add 1 to the number (increment the number represented by the digits). The digits are stored such that the most significant digit is first element of array.

Examples​

Example 1:

Input: 
N = 3
arr[] = {1, 2, 4}
Output:
1 2 5
Explanation:
124+1 = 125, and so the Output

Example 2:

Input: 
N = 3
arr[] = {9,9,9}
Output:
1 0 0 0
Explanation:
999+1 = 1000, and so the output

Your Task​

You don't need to read input or print anything. You only need to complete the function increment() that takes an integer N, and an array arr of size N as input and returns a list of integers denoting the new number which we get after adding one to the number denoted by the array arr.

Expected Time Complexity: O(n)O(n)

Expected Auxiliary Space: O(1)O(1) for iterative approach.

Constraints​

  • 1 ≤ n ≤ 10^5

Problem Explanation​

Given a non-negative number represented as a list of digits, add 1 to the number (increment the number represented by the digits). The digits are stored such that the most significant digit is first element of array.

Code Implementation​

Written by @arunimad6yuq
def increment(digits):
for i in range(len(digits) - 1, -1, -1):
if digits[i] == 9:
digits[i] = 0
else:
digits[i] += 1
return digits
digits.insert(0, 1)
return digits

Time Complexity​

  • The iterative approach has a time complexity of O(n)O(n).

Space Complexity​

  • The space complexity is O(1)O(1) since we are using only a fixed amount of extra space.